package com.chenxys.algorithm.leetcode;

import com.chenxys.algorithm.common.ListNode;

/**
 * <p>
 *      对一个单链表分组，并逆序最后返回<br/>
 *      <a href="https://leetcode.com/problems/reverse-nodes-in-k-group/">原题</a>
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.leetcode
 * @date 12/29/23 12:49 AM
 * @Copyright ©
 */
@SuppressWarnings("all")
public class LeetCode25 {
    // 结构类
    /*public static class ListNode {
        public int value;
        public ListNode next;
    }*/

    // 第一步,先将链表的第k个节点返回

    /**
     * <p>
     *     传入一个单链表,返回第k个节点
     * </p>
     * @param start 单链表
     * @param k 某个节点
     * @return 指定节点
     */
    public static ListNode getGroupEnd(ListNode start, int k){
        // k为正整数,如果k-- > 0,则当前节点一直向下移动
        while (--k != 0 && start != null) {
            start = start.next;
        }
        return start;
    }

    /**
     * <p>
     *     在节点start和end之间逆序
     * </p>
     * @param start 开始的节点
     * @param end 结束的节点
     */
    public static void reverse(ListNode start, ListNode end){
        // 记录end节点的下一个节点
        end = end.next;
        // 定义上一个节点,下一个节点,当前节点
        ListNode pre = null;
        ListNode next = null;
        // 当前节点指向开始节点
        ListNode cur = start;
        // 当当前节点不是最后一个节点时,逆序
        while (cur != end) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // 将开始节点的下一个节点指向原结束节点的下一个节点
        start.next = end;
    }

    /**
     * <p>
     *     传入一个待分组逆序的单链表
     * </p>
     * @param head 待分组逆序的单链表
     * @param k 几个一组
     * @return 逆序后的单链表
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        // 开始节点指向原链表
        ListNode start = head;
        // 获取第一次分组后的尾节点
        ListNode end = getGroupEnd(start, k);
        // 如果不够k个节点,直接返回原链表
        if (end == null) {
            return head;
        }
        // 第一组够k个节点
        // 将头指针指向获取到的尾节点
        head = end;
        // 逆序
        reverse(start, end);
        // 上一组的尾节点 第一次是原链表头节点
        ListNode lastEnd = start;
        while (lastEnd.next != null) {
            // 头指针来到上一组的尾节点的下一个节点
            start = lastEnd.next;
            // 再次获取下一组的尾节点
            end = getGroupEnd(start, k);
            // 不够k个节点
            if (end == null) {
                return head;
            }
            // 够k个节点
            reverse(start, end);
            lastEnd.next = end;
            lastEnd = start;
        }
        return head;
    }
}
